1. Field of the Invention
The present invention relates to a new disk scheduling algorithm for supporting simultaneous read and write requests that are made by the user in the presence of real-time requirements that are associated with these requests.
2. Description of Background Art
Video-on-demand and video authoring tools are emerging as very interesting and challenging multimedia applications. They require special hardware and networking protocols that can accommodate the real-time demands of these applications as well as the high bandwidth that they need.
Several video server architectures are proposed for handling video-on-demand applications. "A Video Server Using ATM Switching Technology," Y. Ito and T. Tanaka, in The 5th International Workshop on Multimedia Communication, pages 341-346, May 1994; "A File System for Continuous Media", David Anderson, Yoshitomo Osawa, and Ramesh Govindan, ACM Trans. Computer Systems, 10(4):311-337, 1992; "Designing An On-Demand Multimedia Service", P. V. Rangan, H. M. Vin, and S. Ramanathan, IEEE Communication Magazine, pages 56-64, July 1992. The present invention is well adapted to work on a server architecture such as the one proposed in The 5th International Workshop on Multimedia Communication that uses multiple disks and file servers that are internally connected by an ATM network. The invention may be implemented on other architectures, as well. Several performance studies and simulations have been conducted to estimate the performance of this system.
A video server can support a variety of applications. Among these applications are: video-on-demand, and video authoring or editing. Each application has its own system requirements. Our focus here is on the disk scheduling requirements of such systems. For example, from the disk's point of view, video-on-demand applications issue read-only requests to the disk, while video editing applications issue both read and write requests. Moreover, some applications may issue read and/or write requests that may or may not have real-time deadlines so that these requests have to be serviced before the deadlines. For example, in video-on-demand, each read request has to be fulfilled within a given deadline. Finally, some applications may allow some of its read or write requests to be lost by the system, i.e., they are not serviced or fulfilled by the disk. For example, some frames can be lost during video viewing due to congestion in the disk.
More formally, from the disk scheduling point of view, we classify read and write requests into four categories, where each category has different requirements and is useful for a certain class of applications. These categories are:
1. dl requests: these are read or write requests that have deadlines and the requests may be lost in the case of congestion. Read and write requests of this category are referred to as R.sub.dl, and W.sub.dl, respectively. PA1 2. dn requests: these are read or write requests that have deadlines and the requests may not be lost regardless of the congestion in the system. Read and write requests of this category are referred to as R.sub.dn and W.sub.dn, respectively. PA1 3. nl requests: there are read or write requests that have no deadlines and the requests may be lost in case of congestion. Read and write requests of this category are referred to as R.sub.nl and W.sub.nl, respectively. PA1 4. nn requests: these are read or write requests that have no deadlines and the requests may not be lost regardless of the congestion in the system. Read and write requests of this category are referred to as R.sub.nn and W.sub.nn, respectively.
For example, the application requirement in the case of video-on-demand is that the disk scheduling process must support only R.sub.dl requests, i.e., read requests that have deadlines but can be lost in case the requests do not get serviced before their deadlines.
Different disk scheduling processes need to be designed for each category of requests. Notice that for the requests that belong to the category nl (whether W.sub.nl or R.sub.nl), since there are no deadlines, it is always true that these requests can be delayed until they are satisfied. Therefore, it makes no sense for the system to lose them as they can afford to wait until they get serviced. As a result, W.sub.nl and R.sub.nl are treated here as W.sub.nn and R.sub.nn, respectively, since they have no deadline and will never be lost. As a result, disk scheduling techniques for only the dl, dn, and nn categories are expressly considered here.